package com.cskaoyan.javase.recursion._2hanoi;

/**
 * 首先看一下汉诺塔问题的描述：
 * 相传在古印度的圣庙中，有一种被称之为汉诺塔（也叫河内塔，Hanoi）的游戏
 * 简单来说：有三个塔1，2，3，塔1上有 N 个（N>1）穿孔圆盘，大盘在下，小盘在上
 * 要求按下列规则将所有圆盘移至塔3：
 * 	1，每次只能移动一个圆盘
 * 	2，大盘一定在小盘之下
 * 提示：可将圆盘临时置于塔2，也可以将塔1的圆盘重新移回塔1，但都必须遵循上述两条规则
 * 问：当塔1上有N（N>=1）个圆盘时，最少要移动多少次？（注意是最少）
 *
 * 设对于n个盘子的汉诺塔问题,至少需要f(n)步完成
 * n = 1 ,至少1步就完成了
 * n = 2 ,至少3步就完成了
 * n = 3 ,至少7步就完成了
 * ....
 * 想要用递归求解汉诺塔问题,要往"分解"的思路上靠
 * 如何分解n个盘子的汉诺塔问题呢?
 * 要想完成n个盘子的汉诺塔问题,必不可少的一步是:
 * 将最大的盘子从塔1到塔3
 * 为了完成这一步,需要:
 * 塔1上所有的除了最大盘子外的所有盘子(n-1)都在塔2上,这一步相当于把(n-1)个盘子,从塔1移到塔2,这个过程需要借助塔3完成
 * 这其实就是n-1个盘子的汉诺塔问题,至少需要f(n-1)步完成
 * 完成上述步骤后,就可以把最大的盘子从塔1放到塔3上去,共需要1步完成
 * 接下来,将n-1个盘子,从塔2全部移到塔3,这个过程需要借助塔1完成
 * 这实际上也是n-1个盘子的汉诺塔问题,至少需要f(n-1)步完成
 * 至此,完成汉诺塔问题求解.
 *
 * 所以分解出来的结果是:
 * f(n) = f(n-1) + 1 + f(n-1); (递归的递归体)
 * 但是以上分解不可能无休止分解
 * f(1) = 1 (递归的出口)
 *
 * 已知f(n) = f(n-1) + 1 + f(n-1),求解f(n)的通项公式.
 * f(n) = 2f(n-1) + 1
 *
 * f(n) + 1 = 2f(n-1) + 2
 * f(n) + 1 = 2(f(n-1) + 1)
 * f(n) + 1 / (f(n-1) + 1) = 2 是典型的等比数列
 * f(n) + 1 = 2^n
 * f(n) = 2^n - 1
 *
 * @since 11:29
 * @author wuguidong@cskaoyan.onaliyun.com
 */
public class Demo {
    public static void main(String[] args) {
        System.out.println(hanoi(5));
    }

    public static long hanoi(int n) {
        // 递归的出口
        if (n == 1) {
            return 1;
        }
        // 递归体
        return hanoi(n - 1) + 1 + hanoi(n - 1);
    }
}
